package arithmetic;

import java.util.*;
import java.lang.*;

/**
 * 二分插入排序 二分插入排序在插入排序的基础上进行了改进，通过不断地分区来快速找到需要插入的位置，
 * 在顺序比较混乱时，效率要比插入排序高很多，但在排序基本完成是，效率要比插入要低。
 */
public class Binary_insertion_sort {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("Please input nine number:");
        int[] a = new int[9];
        for (int j = 0; j < 9; j++) {
            a[j] = in.nextInt();
        }
        int l = 9;
        int temp;
        int low, high;//左、右指针
        int m;
        for (int i = 1; i < l; i++) {
            if (a[i] < a[i - 1]) {
                low = 0;
                high = i - 1;
                while (low <= high) {
                    //利用二分查找到比a[i]还小的索引下标
                    m = low + (high - low) >> 1;
                    if (a[m] > a[i])
                        high = m - 1;
                    else
                        low = m + 1;
                }
                temp = a[i];
                //循环结束 把前面排好的数字以此向后移动一位
                for (int j = i; j > low; j--) {
                    a[j] = a[j - 1];
                }
                //把a[i]插入到low后面 执行下一轮的for循环
                a[low] = temp;
            }
        }
        for (int element : a) {
            System.out.println(element);
        }
    }
}
